import java.util.Arrays;
import java.util.Random;


public class Quicksort {
	public static void main(String[] args){
		int[] vals = {34,3,5,6,7,3,8,9,0,0,2,3,4,1,34,223,1,44,521};
		int[] bigVals = new int[1000];
		for(int i = 0; i < 1000; ++i){
			bigVals[i] = (new Random()).nextInt();
		}
		quicksort(vals, 0, vals.length-1);
		System.out.println(Arrays.toString(vals));
		quicksort(bigVals, 0, 999);
		System.out.println(Arrays.toString(bigVals));
		System.out.println(checkArray(bigVals));
	}
	/**
	 * sorts the elements array between the left and right indices (inclusive)
	 * @param elements
	 * @param left
	 * @param right
	 */
	public static void quicksort(int[] elements, int left, int right){
		if(right-left > 1){
			int pivot = elements[left];
			int split = partition(elements, left+1, right, pivot);
			int a = elements[left];
			elements[left] = elements[split-1];
			elements[split-1] = a;
			quicksort(elements, left, split-1);
			quicksort(elements, split, right);
			
		}
		else {
			
		}
	}
	
	/**
	 * Returns an index of the array, such that all elements, between left and right,
	 * have the property that if their index is less than the returned value, 
	 * then they are less than the pivot.
	 * @param elements
	 * @param left
	 * @param right
	 * @param pivot
	 * @return
	 */
	public static int partition(int[] elements, int left, int right, int pivot){
		int split = left, current = left;
		while(current <= right){
			if(elements[current] < pivot){
				int a = elements[current];
				elements[current] = elements[split];
				elements[split] = a;
				split++;
				current++;
			}
			else{
				current++;
			}
			
		}
		return split;
	}
	public static boolean checkArray(int[] toCheck){
		boolean sorted = true;
		for(int i = 0; i < toCheck.length -1; ++i){
			sorted = sorted && toCheck[i] <= toCheck[i+1];
		}
		return sorted;
	}
	
}
